package com.example.sort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
 * 桶排序
 */
public class BucketSort {
    public static void bucketSort(double[] arr) {
        if (arr.length <= 0) return;
        // 确定桶的数量
        int bucketCount = arr.length;
        // 创建桶
        List<List<Double>> buckets = new ArrayList<>(bucketCount);
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }
        // 将数据映射到桶中
        for (double value : arr) {
            int bucketIndex = (int) (value * bucketCount);
            // 对于等于 1 的情况，防止数组越界
            if (bucketIndex == bucketCount) {
                bucketIndex--;
            }
            buckets.get(bucketIndex).add(value);
        }
        // 对每个桶进行排序并合并
        int index = 0;
        for (List<Double> bucket : buckets) {
            // 对每个桶中的元素进行插入排序（这里使用 Collections.sort）
            Collections.sort(bucket);
            // 将排序后的元素放回原数组
            for (double value : bucket) {
                arr[index++] = value;
            }
        }
    }
    public static void main(String[] args) {
        double[] arr = {0.89, 0.45, 0.34, 0.67, 0.23};
        bucketSort(arr);
        for (double i : arr) {
            System.out.print(i + " ");
        }
    }
}